//
// Created by wangwanlong on 2024/6/24.
//

#ifndef MCGPP_SA_REFINER_H
#define MCGPP_SA_REFINER_H

#include "refiner_base.h"
#include "sp_set.h"

namespace mcgpp {
  class SaRefiner : public RefinerBase {
  public:
    SaRefiner(ds::GenericGraph &graph) : RefinerBase(graph){
      t0 = 0.000017;
      cr = 0.98;
      _performed_moves.reserve(graph.initialNumNodes());//用于回滚
    }

    virtual void initializeImpl() override {
      metrics::conductance(_g, current_obj);
      best_obj = current_obj;
      saveBestSol();

      cut_nodes.clear();
      for (auto u: _g._current_node_set) {
        if (isBorderNode(u))
          cut_nodes.add(u);
      }

      calInitTemp();
    }

    //计算初始温度
    void calInitTemp() {
      double l = 1e-20;
      double r = 1.0;
      Metrics new_obj;
      int move_count = 0;
      int salter = 200000;
//      double x = fabs(l - r);
      while (fabs(l - r) > 1e-20) {
        double mid = (l + r) / 2.0;
        t0 = mid;
        move_count = 0;
        for (int i = 1; i <= salter; ++i) {
          IDType v = cut_nodes[Randomize::instance().getRandomInt(0, cut_nodes.size() - 1)];
          ll delta = moveNodeGain(v, _g.partID(v), 1 - _g.partID(v), current_obj, new_obj);
          bool accept = false;
          if (delta > 0) {
            double d = static_cast<double>(delta / 1e10);
            double x = exp(-d / t0);
            int prob = static_cast<int>(1e6 * x);
            if (Randomize::instance().getRandomInt(0, 1000000 - 1) < prob)
              accept = true;
          }
          if (delta <= 0 || accept) {
            ++move_count;
          }

        }

        int accept_rate = static_cast<double>(move_count * 1.0 / salter) * 100;
//        LOG<<"accept rate:"<<static_cast<double>(accept_rate/100.0);
        if (abs(accept_rate - 50) < 5)
          break;

        if (accept_rate > 50)
          r = mid;
        else
          l = mid;


      }
      t0 /= 4.0;
      LOG << "init t:" << t0;
    }

    //计算初始温度：区别是真的会移动，之后会回滚
    void calInitTemp2() {
      double l = 1e-20;
      double r = 1.0;
      Metrics obj_backup = current_obj;//备份
      int move_count = 0;
      int accept_rate = 0;
      int salter = 200000;
      Metrics new_obj;

      while (fabs(l - r) > 1e-20) {
        double mid = (l + r) / 2.0;
        t0 = mid;
        move_count = 0;
        for (int i = 1; i <= salter && !Timer::instance().TLE(); ++i) {
          IDType v = cut_nodes[Randomize::instance().getRandomInt(0, cut_nodes.size() - 1)];
          ll delta = moveNodeGain(v, _g.partID(v), 1 - _g.partID(v), current_obj, new_obj);
          bool accept = false;
          if (delta > 0) {
            double d = static_cast<double>(delta / 1e10);
            double x = exp(-d / t0);
            int prob = static_cast<int>(1e6 * x);
            if (Randomize::instance().getRandomInt(0, 1000000 - 1) < prob)
              accept = true;
          }
          if (delta <= 0 || accept) {
            current_obj = new_obj;
            ++move_count;
            _performed_moves.push_back(v);//保存移动
            changeNodePart(v, _g.partID(v), 1 - _g.partID(v));
          }
        }
        //计算接受率
        accept_rate = static_cast<double>(move_count * 1.0 / salter) * 100;
        if (abs(accept_rate - 50) < 5)
          break;

        if (accept_rate > 50)
          r = mid;
        else
          l = mid;
      }
      //回滚到初始解
//      current_obj = obj_backup;
//      while (_performed_moves.size()){
//        IDType v = _performed_moves.back();
//        changeNodePart(v, _g.partID(v), 1 ^ _g.partID(v));
//        _performed_moves.pop_back();
//      }
      //check
//      checkDataStructure();
      LOG << "init t:" << t0<<"accpet rate:"<<accept_rate;
    }



    void refineImpl() override {
      int move_count = 0;
      int threshold = 0;
      int salter = 200000;
      Metrics new_obj;


//      checkDataStructure();


      while (!Timer::instance().TLE()) {
        move_count = 0;
        for (int i = 1; i <= salter && !Timer::instance().TLE(); ++i) {
          IDType v = cut_nodes[Randomize::instance().getRandomInt(0, cut_nodes.size() - 1)];
          ll delta = moveNodeGain(v, _g.partID(v), 1 - _g.partID(v), current_obj, new_obj);
          bool accept = false;
          if (delta > 0) {
            double d = static_cast<double>(delta / 1e10);
            double x = exp(-d / t0);
            int prob = static_cast<int>(1e6 * x);
            if (Randomize::instance().getRandomInt(0, 1000000 - 1) < prob)
              accept = true;
//            if (Randomize::instance().getRandomFloat(0.0, 1.0) < x)
//              accept = true;
          }
          if (delta <= 0 || accept) {
            current_obj = new_obj;
            ++move_count;
            changeNodePart(v, _g.partID(v), 1 - _g.partID(v));
//            {
//              //tmp check
//              int cut = 0;
//              for (int k = 0; k < _g._num_edges; ++k) {
//                if (_g.edgeIsEnabled(k) && _g._connectivity_sets[k].bit() == 3)
//                  cut += _g.edge(k).weight();
//              }
//              if(cut != current_obj.cut_weight){
//                _g.check();
//                LOG<<cut<<current_obj.cut_weight;
//                ERROREXIT("eror!");
//              }
//            }
            if (current_obj.conductance < best_obj.conductance) {
              DBG << "better obj" << static_cast<double>(current_obj.conductance / 1e10);
              saveBestSol();
            }

          }

        }
        t0 *= cr;


//        LOG<<"accept rate:"<<static_cast<double>(move_count/static_cast<double>(salter));
        if (move_count * 100 < 5 * salter)
          ++threshold;
        else
          threshold = 0;

        if (threshold == 5)
          break;

        //print info
//        LOG<<t0 << "cur obj"<<std::fixed<<std::setprecision(10) << static_cast<double>(current_obj.conductance / 1e10)
//            <<std::setprecision(3)<< static_cast<double>(move_count * 1.0 / salter);

      }

//
//      DBG << "after sa obj =" << static_cast<double>(current_obj.conductance / 1e10);
//      checkDataStructure();

      //恢复最优解
      current_obj = best_obj;
      for (auto v: _g._current_node_set) {
        if (_g.partID(v) != best_partition[v])
          changeNodePart(v, _g.partID(v), 1 - _g.partID(v));

      }

//      checkDataStructure();

      DBG << "after sa obj =" << static_cast<double>(current_obj.conductance / 1e10);

    }


    //还原搜索

    void borderDescenctSearch(std::vector<IDType> &refine_nodes) override {
//      Randomize::instance().shuffleVector(refine_nodes, refine_nodes.size());
//      Metrics temp_obj;
//      bool improve = false;
//
//      for (auto v: _g._current_node_set) {
//        if (isBorderNode(v) == false)
//          continue;
//        ll delta = moveNodeGain(v, _g.partID(v), 1 - _g.partID(v), _current_obj, temp_obj);
//        if (delta <= 0) {
//          //接受当前移动
//          _g.changeNodePart(v, _g.partID(v), 1 - _g.partID(v));
//          //更新目标函数
//          _current_obj = temp_obj;
//          //如果可以的话更新最优解
//          if (_current_obj.conductance < _best_obj.conductance) {
//            improve = true;
//            LOG << "better obj" << static_cast<double>(_current_obj.conductance / 1e9);
//            saveBestSol();
//          }
//        }
//      }


    }


    double t0;
    double cr;

    std::vector<IDType>_performed_moves;//保存执行的移动，计算初始温度的时候使用

  };
}

#endif //MCGPP_SA_REFINER_H
